package seqlist.LeetCode;
//面试题 02.04. 分割链表

/**
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你不需要保留每个分区中各节点的初始相对位置。
 */

/**
 * 思路一：创建两个新链表。这两个链表就是由原链表组成的。
 * 一个链表存放小于 x 的节点。
 * 一个链表存放大于等于 x 的节点
 * 然后小链表连接大链表就成功了。
 */
public class 面试题_Num02_04_partition {

    public ListNode partition(ListNode head, int x) {
        //边界--判空
        if(head == null || head.next == null){
            return head;
        }

        //存放小于x的链表
        ListNode dummyHead1 = new ListNode();
        ListNode prve1 = dummyHead1;//尾节点，用于连接

        //存放大于等于x的链表
        ListNode dummyHead2 = new ListNode();
        ListNode prve2 = dummyHead2;//尾节点，用于连接

        //方法1 new新的链表
//        while(head != null){
//            if(head.val < x){
//                prve1.next = new ListNode(head.val);
//                prve1 = prve1.next;//后移
//            }else{
//                prve2.next = new ListNode(head.val);
//                prve2 = prve2.next;//后移
//            }
//            head = head.next;
//        }

        //方法2 原地修改
        while(head != null){
            if(head.val < x){
                prve1.next = head;
                prve1 = prve1.next;
                head = head.next;

                prve1.next = null;//切断后面的连接

            }else{
                prve2.next = head;
                prve2 = prve2.next;
                head = head.next;

                prve2.next = null;//切断后面的连接

            }
        }
        //小链表连接大链表
        prve1.next = dummyHead2.next;

        return dummyHead1.next;
    }
}
